UVa/12320 - Flight Control/12320.2.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 template <class T> string toStr(const T &x) { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x) { stringstream s; s << x; int r; s >> r; return r; }
  25
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  28 #define D(x) cout << #x " = " << (x) << endl
  29
  30 const double EPS = 1e-10;
  31
  32 int cmp(double x, double y = 0, double tol = EPS){
  33     return( x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  34 }
  35
  36 struct point {
  37     double x, y, z;
  38     point(){} point(double x, double y, double z) : x(x), y(y), z(z) {}
  39 };
  40
  41 int R[2], V[2];
  42 vector< point > P[2];
  43 double D[2][105];
  44
  45 inline double dist(const point &a, const point &b) {
  46     double dx = b.x - a.x, dy = b.y - a.y, dz = b.z - a.z;
  47     return sqrt(dx * dx + dy * dy + dz * dz);
  48 }
  49
  50 bool lessThan(double a, double b) {
  51     cmp(a, b) < 0;
  52 }
  53
  54 point positionAt(int p, double t) {
  55     double d = V[p] * t;
  56
  57     int i = upper_bound(D[p], D[p] + P[p].size(), d) - D[p] - 1;
  58     assert(i >= 0);
  59     double s = D[p][i];
  60     double distance = dist(P[p][i], P[p][i+1]);
  61     assert(cmp(s + distance, d) >= 0);
  62     point ans = P[p][i];
  63     if (cmp(distance, 0.0) > 0) {
  64         double dx = P[p][i+1].x - P[p][i].x;
  65         double dy = P[p][i+1].y - P[p][i].y;
  66         double dz = P[p][i+1].z - P[p][i].z;
  67         ans.x += (d - s) * dx / distance;
  68         ans.y += (d - s) * dy / distance;
  69         ans.z += (d - s) * dz / distance;
  70     }
  71     assert(cmp(s + dist(P[p][i], ans), d) == 0);
  72     return ans;
  73 }
  74
  75 int main(){
  76     int casos; scanf("%d", &casos); while (casos--) {
  77         for (int p = 0; p < 2; ++p) {
  78             int k; scanf("%d %d %d", &R[p], &V[p], &k);
  79             P[p].resize(k);
  80             for (int i = 0; i < k; ++i) {
  81                 scanf("%lf %lf %lf", &P[p][i].x, &P[p][i].y, &P[p][i].z);
  82             }
  83             P[p].push_back( point(0, 0, 0) );
  84         }
  85
  86         double totalTime = 1e100;
  87         for (int p = 0; p < 2; ++p) {
  88             D[p][0] = 0.0;
  89             for (int i = 1; i < P[p].size(); ++i) {
  90                 D[p][i] = D[p][i-1] + dist(P[p][i-1], P[p][i]);
  91             }
  92             totalTime = min(totalTime, D[p][P[p].size() - 1] / V[p]);
  93         }
  94         //D(totalTime);
  95         int iterations = 40000;
  96         double delta = totalTime / iterations;
  97         // point p1 = positionAt(0, totalTime);
  98         // point p2 = positionAt(1, totalTime);
  99         // printf("<%lf, %lf, %lf>\n", p1.x, p1.y, p1.z);
 100         // printf("<%lf, %lf, %lf>\n", p2.x, p2.y, p2.z);
 101         int ans = 0;
 102         bool outside = true;
 103         for (int i = 0; i <= iterations; ++i) {
 104             double distance = dist(positionAt(0, i * delta), positionAt(1, i * delta));
 105             if (cmp(distance, 1.0 * (R[0] + R[1])) <= 0) {
 106                 if (outside) ans++;
 107                 outside = false;
 108             } else {
 109                 outside = true;
 110             }
 111         }
 112         printf("%d\n", ans);
 113     }
 114     return 0;
 115 }